package com.example.Arithmetic.Arithmetic;

import com.google.common.hash.Hashing;

import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 日期：2023/12/25
 * 时间：9:50
 * 描述：哈希表实现
 *
 * @author songj
 */
public class HashTable {
    //    节点类
    static class Entry {
        int hash;    //哈希码
        Entry next; //下一个
        Object key;
        Object value;

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    Entry[] table = new Entry[16];
    int size = 0;      //元素个数
    float loadFactor = 0.75f;   //负载因子   数组长度*负载因子=阈值
    int threshold = (int) (table.length * loadFactor);


    //    根据hash码获取value
    private Object get(int hash, Object key) {
//        数组长度-1按位与&运算就可以取余
        int index = hash & (table.length - 1);
        if (table[index] == null) {
            return null;
        }
        Entry entry = table[index];
        while (entry != null) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
            entry = entry.next;
        }
        return null;
    }

    //    向哈希表中插入数据，如果key重复，则更新value
    private void put(int hash, Object key, Object value) {
        int index = hash & (table.length - 1);
//        hashTable无值，新增
        if (table[index] == null) {
            table[index] = new Entry(hash, key, value);
        } else {
//            有值，更新
            Entry entry = table[index];
            while (true) {
                if (entry.key.equals(key)) {
                    entry.value = value;
                    return;
                }
                if (entry.next == null) {
                    break;
                }
                entry = entry.next;
            }
//           entry无值，新增,p代表最后一个位置，新增到最后
            entry.next = new Entry(hash, key, value);
        }
        size++;
        if (threshold < size) {
            resize();
        }
    }

    private void resize() {
//        新hash表
        Entry[] newTable = new Entry[table.length << 1];
        for (int i = 0; i < table.length; i++) {
            Entry p = table[i];     //拿到每一个链表头
            if (p != null) {
                /**
                 * 拆分链表，移动新数组，差分规律
                 * 一个链表最多拆成两个
                 * hash&table.length==i的一组
                 *hash&table.length！=i的一组
                 */
                Entry a = null;
                Entry b = null;
                Entry aHead = null;
                Entry bHead = null;
                while (p != null) {
                    if ((p.hash & table.length) == 0) {
                        if (a != null) {
                            a.next = p;
                        } else {
//                            初值，第一次来执行
                            aHead = p;
                        }
                        a = p;
                    } else {
                        if (b != null) {
                            b.next = p;
                        } else {
//                            初值，第一次来执行
                            bHead = p;
                        }
                        b = p;
                    }
                    p = p.next;
                }
//                ab下一个指针都置为null
                if (a != null) {
                    a.next = null;
                    newTable[i] = aHead;
                }
                if (b != null) {
                    b.next = null;
                    newTable[table.length + i] = bHead;
                }
            }
        }
        table = newTable;
        threshold = (int) (table.length * loadFactor);
    }

    // 根据hash码删除，返回value
    private Object remove(int hash, Object key) {
        int index = hash & (table.length - 1);
        if (table[index] == null) {
            return null;
        }
        Entry entry = table[index];
        Entry last = null;
        while (entry != null) {
            if (entry.key.equals(key)) {
//               找到了，删除
                if (last == null) {
                    table[index] = entry.next;
                } else {
                    last.next = entry.next;
                }
                size--;
                return entry.value;
            }
            last = entry;
            entry = entry.next;
        }
        return null;
    }

    public Object get(Object key) {
        return get(getHashCode(key), key);
    }

    public void put(Object key, Object value) {
        put(getHashCode(key), key, value);
    }

    public Object remove(Object key) {
        return remove(getHashCode(key), key);
    }

    private static int getHashCode(Object key) {
        if (key instanceof String k){
            return Hashing.murmur3_32().hashString(k, StandardCharsets.UTF_8).asInt();
        }
        int i = key.hashCode();
        return i^(i>>>16);
    }

    public void prant() {
        int[] sunms = new int[table.length];
        for (int i = 0; i < table.length; i++) {
            Entry entry = table[i];
            while (entry != null) {
                sunms[i]++;
                entry = entry.next;
            }
        }
        Map<Integer, Long> collect = Arrays.stream(sunms).boxed().collect(Collectors.groupingBy(e -> e, Collectors.counting()));
        System.out.println(collect);
    }


}
